#pragma once
#ifndef __BalanceTree_H__    
#define __BalanceTree_H__   

#include<iostream>
#include<vector>
#include<queue>
#include <iomanip>
#include <iostream>
using namespace std;


template<typename Comparable>
class AvlTree
{
public:
	struct AvlNode
	{
		Comparable element;
		AvlNode* left;
		AvlNode* right;
		int  height;
		AvlNode(const Comparable& ele, AvlNode* lt, AvlNode* rt, int h = 0)
			: element{ ele }, left{ lt }, right{ rt }, height{ h }{ }
		AvlNode(Comparable&& ele, AvlNode* lt, AvlNode* rt, int h = 0)
			: element{ std::move(ele) }, left{ lt }, right{ rt }, height{ h }{ }
	};
	AvlNode* root;
	AvlTree()
	{
		root = nullptr;
	}
	bool isEmpty()const
	{
		if (this == nullptr)
			return 1;
		else
			return 0;
	}
	/*
	* return the height of node t or -1 if nullptr.
	*/
	int height(AvlNode* t)const
	{
		return t == nullptr ? -1 : t->height;
	}
	void insert(const Comparable& x)
	{
		insert(x, root);
	}
	/**
	*Internal method to insert into a subtree.
	* x is the item to insert.
	* t is the node that roots the subtree.
	* set the new root of the subtree.
	*/
	void insert(const Comparable& x, AvlNode*& t)
	{
		if (t == nullptr)
			t = new AvlNode{ x, nullptr, nullptr };
		else if (x < t->element)
			insert(x, t->left);
		else if (t->element < x)
			insert(x, t->right);

		balance(t);
	}

	static const int ALLOWED_IMBALANCE = 1;

	//Assume t is balanced or within one of being balanced
	void balance(AvlNode*& t)
	{
		if (t == nullptr)
			return;
		if (height(t->left) - height(t->right) > ALLOWED_IMBALANCE)
			if (height(t->left->left) >= height(t->left->right))
				rotateWithLeftChild(t);
			else
				doubleWithLeftChild(t);
		else
			if (height(t->right) - height(t->left) > ALLOWED_IMBALANCE)
				if (height(t->right->right) >= height(t->right->left))
					rotateWithRightChild(t);
				else
					doubleWithRightChild(t);

		t->height = max(height(t->left), height(t->right)) + 1;

	}
	/**
	* Rotate binary tree node with left child.
	* For AVl trees, this is a single rotation for case 1.
	* Update heights, then set new root.
	*/
	void rotateWithLeftChild(AvlNode*& k2)
	{
		AvlNode* k1 = k2->left;
		k2->left = k1->right;
		k1->right = k2;
		k2->height = max(height(k2->left), height(k2->right)) + 1;
		k1->height = max(height(k1->left), k2->height) + 1;
		k2 = k1;
	}
	void rotateWithRightChild(AvlNode*& k2)
	{
		AvlNode* k1 = k2->right;
		k2->right = k1->left;
		k1->left = k2;
		k2->height = max(height(k2->left), height(k2->right)) + 1;
		k1->height = max(height(k1->right), k2->height) + 1;
		k2 = k1;
	}
	/**
	* Double rotate binary tree node: first left child.
	* with its right child; then node k3 with new left child.
	* For AVL trees, this is a double rotation for case 2.
	* Update heights, then set new root.
	*/
	void doubleWithLeftChild(AvlNode*& k3)
	{
		rotateWithRightChild(k3->left);
		rotateWithLeftChild(k3);
	}
	void doubleWithRightChild(AvlNode*& k3)
	{
		rotateWithLeftChild(k3->right);
		rotateWithRightChild(k3);
	}
	void remove(const Comparable& x)
	{
		remove(x, root);
	}
	/**
	* Internal method to remove from a subtree.
	* x is the item to remove.
	* t is the node that roots the subtree.
	* Set the new root of the subtree.
	*/
	void remove(const Comparable& x, AvlNode*& t)
	{
		if (t == nullptr)
			return;  //Item not found; do nothing.
		if (x < t->element)
			remove(x, t->left);
		else if (t->element < x)
			remove(x, t->right);
		else if (t->left != nullptr && t->right != nullptr)//Two children.
		{
			t->element = findMin(t->right)->element;
			remove(t->element, t->right);
		}
		else
		{
			AvlNode* oldNode = t;
			t = (t->left != nullptr) ? t->left : t->right;
			delete oldNode;
		}

		balance(t);
	}
	const Comparable& findMin()const
	{
		if (findMin(root) == nullptr)  return 0;
		else   return findMin(root)->element;
	}
	AvlNode* findMin(AvlNode* t)const
	{
		if (t == nullptr)
			return nullptr;
		if (t->left == nullptr)
			return t;
		return findMin(t->left);
	}
	int max(int a, int b)const
	{
		if (a >= b)
			return a;
		else return b;
	}
	void levels_show() {
		levels_show(root);
	}
	void levels_show(AvlNode* root) {//层次遍历,利用队列实现 
		if (root == nullptr)
			return;

		queue<AvlNode*> que;//构造一个树结点指针的队列
		que.push(root);

		while (!que.empty()) {
			AvlNode* q = que.front();
			cout << q->element << " ";
			que.pop();

			if (q->left != nullptr)//que.front()拿到最前结点 
			{
				que.push(q->left);
			}
			else cout << -1 << " ";//左孩子为空则返回-1

			if (q->right != nullptr) {
				que.push(q->right);
			}
			else cout << -1 << " ";//右孩子为空则返回-1
		}
		cout << endl;
	}
};
template<typename Comparable>
void BST_sort(std::vector<Comparable>& _data, AvlTree<Comparable>& b)
{
	cout << "依次插入：" << endl;
	for (unsigned int i = 0; i < _data.size(); i++)
	{
		b.insert(_data[i]);
		cout << _data[i] << " ";
	}
	cout << endl;
}

template <class T>
class SplayTreeNode {
public:
    T key;                
    SplayTreeNode* left;   
    SplayTreeNode* right;   


    SplayTreeNode() :left(nullptr), right(nullptr) {}

    SplayTreeNode(T value, SplayTreeNode* l, SplayTreeNode* r) :
        key(value), left(l), right(r) {}
};

template <class T>
class SplayTree {
private:
    SplayTreeNode<T>* mRoot;  

public:
    SplayTree();
    ~SplayTree();
    SplayTreeNode<T>* search(T key);
    void splay(T key);
    void insert(T key);
    void remove(T key);
    void destroy();
    void levels_show() {
        levels_show(mRoot);
    }
private:

	//查找结点
    SplayTreeNode<T>* search(SplayTreeNode<T>* x, T key) const;

    //旋转
    SplayTreeNode<T>* splay(SplayTreeNode<T>* tree, T key);

    // 插入节点
    SplayTreeNode<T>* insert(SplayTreeNode<T>*& tree, SplayTreeNode<T>* z);

    // 删除伸展树节点
    SplayTreeNode<T>* remove(SplayTreeNode<T>*& tree, T key);

    // 清除树
    void destroy(SplayTreeNode<T>*& tree);

	void levels_show(SplayTreeNode<T>* mRoot) {//层次遍历,利用队列实现 
		if (mRoot == nullptr)
			return;

		queue<SplayTreeNode<T>*> que;//构造一个树结点指针的队列
		que.push(mRoot);

		while (!que.empty()) {
			SplayTreeNode<T>* q = que.front();
			cout << q->key << " ";
			que.pop();

			if (q->left != nullptr)//que.front()拿到最前结点 
			{
				que.push(q->left);
			}
			else cout << -1 << " ";//左孩子为空则返回-1
			if (q->right != nullptr) {
				que.push(q->right);
			}
			else cout << -1 << " ";//右孩子为空则返回-1
		}
		cout << endl;
	}
};

template <class T>
SplayTree<T>::SplayTree() :mRoot(nullptr)
{
}

template <class T>
SplayTree<T>::~SplayTree()
{
    destroy(mRoot);
}

//查找结点
template <class T>
SplayTreeNode<T>* SplayTree<T>::search(SplayTreeNode<T>* x, T key) const
{
    if (x == nullptr || x->key == key)
        return x;

    if (key < x->key)
        return search(x->left, key);
    else
        return search(x->right, key);
}

template <class T>
SplayTreeNode<T>* SplayTree<T>::search(T key)
{
    return search(mRoot, key);
}


template <class T>
SplayTreeNode<T>* SplayTree<T>::splay(SplayTreeNode<T>* tree, T key)
{
    SplayTreeNode<T> N, * l, * r, * c;

    if (tree == nullptr)
        return tree;

    N.left = N.right = nullptr;
    l = r = &N;

    for (;;)
    {
        if (key < tree->key)
        {
            if (tree->left == nullptr)
                break;
            if (key < tree->left->key)
            {
                c = tree->left;                          
                tree->left = c->right;
                c->right = tree;
                tree = c;
                if (tree->left == nullptr)
                    break;
            }
            r->left = tree;                              
            r = tree;
            tree = tree->left;
        }
        else if (key > tree->key)
        {
            if (tree->right == nullptr)
                break;
            if (key > tree->right->key)
            {
                c = tree->right;                        
                tree->right = c->left;
                c->left = tree;
                tree = c;
                if (tree->right == nullptr)
                    break;
            }
            l->right = tree;                              
            l = tree;
            tree = tree->right;
        }
        else
        {
            break;
        }
    }

    l->right = tree->left;                               
    r->left = tree->right;
    tree->left = N.right;
    tree->right = N.left;

    return tree;
}

template <class T>
void SplayTree<T>::splay(T key)
{
    mRoot = splay(mRoot, key);
}

//将结点插入到伸展树中，并返回根节点
template <class T>
SplayTreeNode<T>* SplayTree<T>::insert(SplayTreeNode<T>*& tree, SplayTreeNode<T>* z)
{
    SplayTreeNode<T>* y = nullptr;
    SplayTreeNode<T>* x = tree;

    while (x != nullptr)
    {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else if(z->key > x->key)
            x = x->right;
    }

    if (y == nullptr)
        tree = z;
    else if (z->key < y->key)
        y->left = z;
    else
        y->right = z;

    return tree;
}

template <class T>
void SplayTree<T>::insert(T key)
{
    SplayTreeNode<T>* z = nullptr;

    if ((z = new SplayTreeNode<T>(key, nullptr, nullptr)) == nullptr)
        return;


    mRoot = insert(mRoot, z);
    mRoot = splay(mRoot, key);
}

// 删除结点(节点的键值为key)，返回根节点
template <class T>
SplayTreeNode<T>* SplayTree<T>::remove(SplayTreeNode<T>*& tree, T key)
{
    SplayTreeNode<T>* x;

    if (tree == nullptr)
        return nullptr;

    if (search(tree, key) == nullptr)
        return tree;

    tree = splay(tree, key);

    if (tree->left != nullptr)
    {
        x = splay(tree->left, key);

        x->right = tree->right;
    }
    else
        x = tree->right;

    delete tree;

    return x;

}

template <class T>
void SplayTree<T>::remove(T key)
{
    mRoot = remove(mRoot, key);
}

template <class T>
void SplayTree<T>::destroy(SplayTreeNode<T>*& tree)
{
    if (tree == nullptr)
        return;

    if (tree->left != nullptr)
        destroy(tree->left);
    if (tree->right != nullptr)
        destroy(tree->right);

    delete tree;
}

template <class T>
void SplayTree<T>::destroy()
{
    destroy(mRoot);
}

#endif